



@inproceedings{panconesi1,
author = {Flavio Chierichetti and Silvio Lattanzi andAlessandro Panconesi},
title ={ Almost tight bounds for rumour spreading with conductance},
booktitle ={STOC},
 year ={2010},
 pages ={399-408}
 }

@inproceedings{panconesi2,
author = {Flavio Chierichetti and Silvio Lattanzi and Alessandro Panconesi},
title ={Rumour spreading and graph conductance},
booktitle ={SODA},
 year ={2010},
 pages ={1657-1663}
 }
 @article{feige-rumor,
 author = {Feige, U. and Peleg, David and Raghavan, P. and Upfal, Eli},
 title = {Randomized broadcast in networks},
 journal= {Random Structures an Algorithms},
 year = {1990},
 volume = {1(4)},
pages = {447-460}
} 

@article{feige1,
  author    = {Uriel Feige},
  title     = {A Tight Upper Bound on the Cover Time for Random Walks on
               Graphs},
  journal   = {Random Struct. Algorithms},
  volume    = {6},
  number    = {1},
  year      = {1995},
  pages     = {51-54}
}

@article{feige2,
  author    = {Uriel Feige},
  title     = {A Tight Lower Bound on the Cover Time for Random Walks on
               Graphs},
  journal   = {Random Struct. Algorithms},
  volume    = {6},
  number    = {4},
  year      = {1995},
  pages     = {433-438}
  }
  
  @article{sicomp,
  author    = {Jen-Yeu Chen and
               Gopal Pandurangan},
  title     = {Almost-Optimal Gossip-Based Aggregate Computation},
  journal   = {SIAM J. Comput.},
  volume    = {41},
  number    = {3},
  year      = {2012},
  pages     = {455-483}
  }

@article{star-internet,
author = {Francesc Comellas and Silvia Gago},
title = {A star based model for the eigenvalue power law of Internet graphs},
journal = {Phys.  A},
volume = {351},
year =  {2005},  
pages = {680-686}
} 
 
@inproceedings{gia1,
author = {George Giakkoupis and Thomas Sauerwald},
title = {Rumor spreading and vertex expansion},
booktitle = {SODA},
year = {2012},
pages = {1623-1641}
}

@inproceedings{pana1,
author = {Nikolaos Fountoulakis and  Konstantinos Panagiotou and Thomas Sauerwald},
title =  {Ultra-fast rumor spreading in social networks},
booktitle = {SODA},
year = { 2012},
pages = {1642-1660}
}

@inproceedings{pana2, 
author = {Nikolaos Fountoulakis and Konstantinos Panagiotou},
title = {Rumor Spreading on Random Regular Graphs and Expanders},
booktitle = {APPROX-RANDOM},
year = {2010},
pages = { 560-573}
}

@article{panconesi3,
author = {Flavio Chierichetti and Silvio Lattanzi and Alessandro Panconesi},
title = {Rumor spreading in social networks},
journal ={Theoretical Computer Science},
 year ={2011},
 volume = {412(24)},
 pages = {2602-2610}
 }


@article{ozalp1,
  title = {T-MAN: Gossip-based fast overlay topology construction},
  author = {M. Jelasity and A. Montresor and O. Babaoglu},
  journal = {Computer networks},
  year = {2009},
  volume = {53},
  pages = {2321-2339}
}

@article{ozalp2,
  title = {Self-* properties through gossiping},
  author = {O. Babaoglu and M. Jelasity},
  journal = {Philosophical Transactions of the Royal Society A},
  year = {2008},
  volume = {366},
  pages = {3747-3757}
}

@inproceedings{berns,
author = {A. Berns and S. Ghosh and S. Pemmaraju},
title = {A framework for building self-stabilizing overlay networks},
booktitle = {PODC},
note = {Brief Announcement},
 year ={2010},
 pages ={398-399}
 }

@inproceedings{jacob,
author = {R. Jacob and A. Richa and C. Scheideler and S. Schmid and H. Taubig},
title = {A distributed polylogarithmic time
algorithm for self-stabilizing skip graphs},
booktitle = {PODC},
 year ={2009},
 pages ={131-140}
 }

@inproceedings{doerr,
author = {B. Doerr and T. Friedrich and T. Sauerwald},
title = {Quasi-random rumor spreading},
booktitle = {SODA},
 year ={2008},
 pages ={773-781}
 }
 
  
 @inproceedings{gia2,
author = {Giakkoupis},
title = {Tight bounds
for rumor spreading in graphs of a
given conductance},
booktitle = {STACS},
 year ={2011},
 pages ={57-68}
 }
 

@book{b1,
  title = {Handbook of Graphs and Networks},  
  author = {S. Bornholdt and H. Schuster (Editors)},
  publisher = {Wiley-VCH},
  year = {2003},
}

@book{b2,
  title = {Structure and Dynamics of Networks},  
  author = {M. J. Newman and A. Barabasi and D. J. Watts},
  publisher = {Princeton University Press},
  year = {2006}
}

@book{b3,
  title = {Complex Social Networks},  
  author = {F. Vega-Redondo},
  publisher = {Cambridge University Press},
  year = {2007}
}

@inproceedings{law-siu,
author = {C. Law and K. Siu},
title = {An {$O(\log n)$} randomized resource discovery
algorithm},
booktitle = {DISC},
note = {Brief Announcement},
 year ={2000},
 pages ={5--8}
 }
 
 @INPROCEEDINGS{frieze1,
    author = {S. Chakrabarti and A. Frieze and J. Vera},
    title = {The Influence of Search Engines on Preferential Attachment},
    booktitle = {SODA},
    year = {2005}
}

 
@INPROCEEDINGS{frieze2,
    author = {C. Cooper and A. Frieze},
    title = {Crawling on Web Graphs},
    booktitle = {STOC},
    year = {2002}
}
 

@article{kuhn+lo:dynamic,
  title = {Distributed Computation in Dynamic Networks},
  author = {F. Kuhn and N. Lynch and R. Oshman},
  journal = {STOC},
  year = {2010},
}

@inproceedings{kempe1, 
author = {D. Kempe and J. Kleinberg},
title ={Protocols and Impossibility Results for Gossip-Based Communication
Mechanisms}, 
booktitle = {FOCS},
year = {2002}
}

@inproceedings{kempe2, 
author = {D. Kempe and J. Kleinberg and A. Demers},
title ={Spatial Gossip and Resource Location Protocols}, 
booktitle = {STOC}, 
year = {2001}
}


@article{chernoff,
  title = {Asymptotic efficiency for tests based on the sum of observations},
  author = {H. Chernoff},
  journal = {Math. Stat.},
  year = {1952},
}

@article{hoeffding,
  title = {Probability for sums of bounded random variables},
  author = {W. Hoeffding},
  journal = {Journal of American Statistical Association},
  year = {1963}
}

@article{angluin,
  title = {Fast probabilistic algorithms for Hamiltonian circuits and matchings},
  author = {D. Angluin and L.G. Valiant},
  journal = {Journal of Computer and System Sciences},
  year = {1979}
}

@book{upfal,
  title = {Probability and Computing: Randomized Algorithms and Probabilistic Analysis},
  author = {M. Mitzenmacher and E. Upfal},
  publisher = {Cambridge University Press},
  year = {2004},
}

@article{jain+ms:steiner,
  title = {Packing Steiner trees},
  author = {K. Jain and M. Mahdian and M. Salavatipour},
  journal = {SODA},
  year = {2003},
}

@article{cheriyan+s:steiner,
  title = {Hardness and Approximation Results for Packing Steiner Trees},
  author = {J. Cheriyan and M. Salavatipour},
  journal = {Algorithmica},
  year = {2006},
}

@article{charikar+ccdgg:steiner,
  title = {Approximation Algorithms for Directed Steiner Problems},
  author = {M. Charikar and C. Chekuri and T. Cheung and Z. Dai and A. Goel and S. Guha},
  journal = {Journal of Algorithms},
  year = {1998},
}

@article{lau:steiner,
  title = {An approximate max-steiner-tree-packing min-steiner-cut theorem},
  author = {L.C. Lau},
  journal = {FOCS},
  year = {2004},
}

@article{guruswami+krsy,
  title = {Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems},
  author = {V. Guruswami and S. Khanna and R. Rajaraman and B. Shepherd and M. Yannakakis},
  journal = {STOC},
  year = {1999},
}

@article{ittai,
 author = {I. Abraham and D. Dolev},
 title = {Asynchronous resource discovery},
 journal = {Computer Networks},
 volume = {50},
 issue = {10},
 month = {July},
 year = {2006},
 issn = {1389-1286},
 pages = {1616--1629},
 numpages = {14},
}

@INPROCEEDINGS{leighton,
    author = {M. Harchol-Balter and T. Leighton and D. Lewin},
    title = {Resource Discovery in Distributed Networks},
    booktitle = {PODC},
    year = {1999},
    pages = {229--237}
}

@inproceedings{kutten,
  title = {Deterministic Resource Discovery in Distributed Networks},
  author = {S. Kutten and D. Peleg and U. Vishkin},
  booktitle = {SPAA},
  year = {2001}
}

@inproceedings{dimitriov+p:coupon,
  author    = {N. B. Dimitrov and
               C. Greg Plaxton},
  title     = {Optimal Cover Time for a Graph-Based Coupon Collector Process},
  booktitle = {ICALP},
  year      = {2005},
  pages     = {702-716},
}

@inproceedings{adler+hkv:p2p,
  author    = {M. Adler and
               E. Halperin and
               R. M. Karp and
               V. V. Vazirani},
  title     = {A stochastic process on the hypercube with applications
               to peer-to-peer networks},
  booktitle = {STOC},
  year      = {2003},
  pages     = {575-584},
}

@article{alon:combinatorics,
    author = {N. Alon},
    title = {Problems and results in extremal combinatorics -- {II}},
    journal = {Discrete Mathematics},
    year = {2003}
}

@inproceedings{chen-spaa,
  author    = {J. Chen and G. Pandurangan},
  title     = {Optimal Gossip-based Aggregate Computation},
  booktitle = {SPAA},
  year      = {2010},
  pages     = {124-133}
}

@inproceedings{demers,
 author = {Alan Demers and Dan Greene and Carl Hauser and Wes Irish and John Larson and Scott Shenker and Howard Sturgis and Dan Swinehart and Doug Terry},
 title = {Epidemic algorithms for replicated database maintenance},
 booktitle = {PODC},
 year = {1987},
 pages = {1--12},
 }

@inproceedings{MIH,
  author    = {Milena Mihail},
  title     = {Conductance and Convergence of Markov Chains-A Combinatorial
               Treatment of Expanders},
  booktitle = {FOCS},
  year      = {1989},
  pages     = {526-531},
}


@inproceedings{shah,
 author = {Damon Mosk-Aoyama and Devavrat Shah},
 title = {Computing separable functions via gossip},
 booktitle = {PODC},
 year = {2006},
 pages = {113--122}
 }

@inproceedings{karp,
 author = {R. M. Karp and C. Schindelhauer and S. Shenker and B. V\"{o}cking},
 title = {Randomized rumor spreading},
 booktitle = {FOCS},
 year = {2000},
 isbn = {0-7695-0850-2},
 pages = {565--574},
 publisher = {},
 address = {},
 }

@article{DRG,
  author =       {J. Chen and G. Pandurangan and D. Xu},
  title =        {Robust aggregate computation in wireless sensor network: distributed randomized algorithms and analysis},
  journal =    {IEEE Trans. on Parallel and Distributed Systems},
  volume        = {17},
  number        = {9},
  year =         {Sep. 2006},
  pages  =       {987--1000},
}

@conference{kempe,
author ={D. Kempe and A. Dobra and J. Gehrke},
title={Gossip-based Computation of
Aggregate Information},
booktitle={FOCS},
year={2003},
pages={482--491},
}

@article{boyd,
 author = {S. Boyd and A. Ghosh and B. Prabhakar and D. Shah},
 title = {Randomized gossip algorithms},
 journal = {IEEE Trans. on Infor. Theory},
 volume = {52},
 number = {6},
 year = {2006},
 pages = {2508--2530}
  }
  
@incollection{lovasz-survey,
author = {L. Lov\'asz},
title = {Random walks on graphs: a survey},
booktitle = {Combinatorics, Paul Erd\"os is Eighty},
year = {1993},
pages = {1-46},
}  
@inproceedings{berenbrink,
  author    = {Petra Berenbrink and
               Colin Cooper and
               Robert Els{\"a}sser and
               Tomasz Radzik and
               Thomas Sauerwald},
  title     = {Speeding Up Random Walks with Neighborhood Exploration},
  booktitle = {SODA},
  year      = {2010},
  pages     = {1422-1435},
}

@inproceedings{DP05,
  author    = {Nedialko B. Dimitrov and
               C. Greg Plaxton},
  title     = {Optimal Cover Time for a Graph-Based Coupon Collector Process},
  booktitle = {ICALP},
  year      = {2005},
  pages     = {702-716},
}

@INPROCEEDINGS{GANESH, 
author={Ganesh, A. and Massoulie, L. and Towsley, D.}, 
booktitle={INFOCOM},
title={The effect of network topology on the spread of epidemics}, 
year={2005}, 
month={march}, 
volume={2}, 
number={}, 
pages={ 1455 - 1466}, }
  
@ARTICLE{KES,
   author = {{Kessler}, D.~A.},
    title = "{Epidemic Size in the {SIS} Model of Endemic Infec- Tions}",
  journal = {ArXiv e-prints},
archivePrefix = "arXiv",
   eprint = {0709.3049},
 primaryClass = "q-bio.PE",
     year = 2007,
    month = sep,
    adsurl = {http://adsabs.harvard.edu/abs/2007arXiv0709.3049K},
}

@article {PIET,
   author = {Van Mieghem, Piet},
   title = {The $N$-intertwined {SIS} epidemic network model},
   journal = {Computing},
   publisher = {Springer Wien},
   issn = {0010-485X},
   keyword = {Computer Science},
   pages = {147-169},
   volume = {93},
   issue = {2},
   url = {http://dx.doi.org/10.1007/s00607-011-0155-y},
   year = {2011}
}

@inproceedings{ER09,
  author    = {Klim Efremenko and
               Omer Reingold},
  title     = {How Well Do Random Walks Parallelize?},
  booktitle = {APPROX-RANDOM},
  year      = {2009},
  pages     = {476-489},
}

    @article{FILL,
     jstor_articletype = {research-article},
     title = {Eigenvalue Bounds on Convergence to Stationarity for Nonreversible Markov Chains, with an Application to the Exclusion Process},
     author = {Fill, James Allen},
     journal = {The Annals of Applied Probability},
     jstor_issuetitle = {},
     volume = {1},
     number = {1},
     jstor_formatteddate = {Feb., 1991},
     pages = {pp. 62-87},
     url = {http://www.jstor.org/stable/2959625},
     language = {English},
     year = {1991},
     publisher = {Institute of Mathematical Statistics},
    }


@inproceedings{Berger:2005:SVI:1070432.1070475,
 author = {Berger, Noam and Borgs, Christian and Chayes, Jennifer T. and Saberi, Amin},
 title = {On the spread of viruses on the internet},
 booktitle = {Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms},
 series = {SODA '05},
 year = {2005},
 isbn = {0-89871-585-7},
 location = {Vancouver, British Columbia},
 pages = {301--310},
 numpages = {10},
 url = {http://dl.acm.org/citation.cfm?id=1070432.1070475},
 acmid = {1070475},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA}, 
} 

@ARTICLE{KAHALE,
    author = {Nabil Kahale},
    title = {Eigenvalues and Expansion of Regular Graphs},
    journal = {Journal of the ACM},
    year = {1995},
    volume = {42},
    pages = {1091--1106}
}


@book{chung2006complex,
  title={Complex graphs and networks},
  author={Chung, F.R.K. and Lu, L. and Conference Board of the Mathematical Sciences and National Science Foundation (U.S.)},
  number={no. 107},
  isbn={9780821836576},
  lccn={2006042898},
  series={CBMS Regional Conference Ser. in Mathematics Series},
  url={http://books.google.com/books?id=BqqDsEKlAE4C},
  year={2006},
  publisher={American Mathematical Society}
}
